#pragma once

#include <vector>
#include <cstring>
#include <string>
#include <map>

class AhoCorasick {
public:
    typedef std::map<unsigned char, int>::iterator MapIterator; //итератор по бору
    struct Match { //структура, возвращаемая в случаем нахождения плохого слова в строке
        int patternIndex; //номер плохого слово
        int textPosition; //позиция начиная с которой произошло совпадение
        Match(int newPatternIndex, int newTextPosition);
    };
    AhoCorasick();
    void addPattern(const std::string& pattern); //добавить строку-образец(плохое слово)
    void addPattern(const std::vector<std::string> patterns); //добавить вектор строк-образцов
    void getMatches(const std::string& text, std::vector<Match>& matches); //получить в matches все вхождения строк-образцов в исходную строку
    std::string getPattern(int patternIndex) const; //возврат строки образца по номеру
private:
    static const unsigned char ALPHABET_START = 'a'; //символ, который является 1ым в нашем алфавите. В алфавите из ангийских букв это 'a'
    
    struct TreeNode { //структура реализующая вершину в боре
        int patternIndex;
        int parentIndex; //номер родителя
        std::map<unsigned char, int> nextCharNode; //map детей
        std::map<unsigned char, int> autoGoNode; //map с ребрами из текущей вершины, заполняется ленивой рекурсией
        int suffLink, suffTermLink; //суффиксная ссылка + хорошая суффиксная ссылка
        bool isTermNode; //флаг показывающий соостветсвует ли данная вершина patter-ну (те является ли завершающей)
        unsigned char wayChar; //символ, соединяющий вершину с предком
        TreeNode(int newParentIndex, unsigned char newWayChar);
    };
    
    std::vector<TreeNode> nodes; //вектор вершин
    std::vector<std::string> patterns; //вектор плохих слов
    
    size_t size() const;
    void searchMatches(int nodeIndex, int textIndex, std::vector<Match>& matches); //поиск совпадений и добавление их в matches
    int getAutoGoNode(int nodeIndex, unsigned char transChar); //возвращает номер вершины, в которую мы попадем при переходе из nodeIndex о символу transChar
    int getSuffLink(int nodeIndex); //поиск суффиксной ссылки
    int getSuffTermLink(int nodeIndex); //поиск хорошей суффиксной ссылки
};